package dem1;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 33013
 * Date: 2023-04-19
 * Time: 19:15
 */

public class Test {

    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if(top.left != null) {
                queue.offer(top.left);
            }
            if(top.right != null) {
                queue.offer(top.right);
            }
        }

    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> list = new List<List<Integer>> ();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            List<Integer> list2 = new ArrayList<>();
            int size = queue.size();
            while (size != 0){
                TreeNode top = queue.poll();
                list2.add(top.val);
                if(top.left != null) {
                    queue.offer(top.left);
                }
                if(top.right != null) {
                    queue.offer(top.right);
                }
                size--;
            }
            list.add(list2);
        }
    }

    public int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
//递归的出口  不满足这个条件 那么就是没有了左树 或者右树
        if(inbegin > inend) {
            return null;
        }
//先创建根节点
        TreeNode root = new TreeNode(preorder[preIndex]);//根节点

//找到根节点 所在中序遍历中的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;
// 先创建左树 再创建右树   本身是在遍历： 前序遍历
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

        return root;
    }

}
